package cn.com.mdx.sort;

import edu.princeton.cs.algs4.StdRandom;

import java.util.Date;
import java.util.Random;

/**
 * <p> 排序方法类
 *
 * @author ：huangy
 * @date ：Created in 2020/8/25 8:39 下午
 */
@SuppressWarnings(value = {"unchecked", "rawtypes"})
public class SortUtils {

    private static final int CUTOFF = 7;
    private static final Random random = new Random();

    /**
     * <p> 冒泡排序
     * 1.一次循环，将数组最大元素放到数组末尾
     * 2.然后在重复上述操作将剩下元素中最大的放到末尾
     * 1) 第一次将数组中最大的5选出来，放到数组后面
     * |4|*5*|1|3|2|
     * |4|1|3|2|*5*|
     * 2) 第二次将剩下的数中最大的4选出来
     * |*4*|1|3|2|5|
     * |1|3|2|*4*|5|
     * 3) 以此类推
     * |1|*3*|2|4|5|
     * |1|2|*3*|4|5|
     * 4）数组已经有序了，结束循环
     *
     * @param array 要排序的数组
     * @return void
     * @Author huangy
     * @description //TODO 冒泡排序
     * @date 9:24 下午 2020/8/26
     **/
    public static void bubblingSort(Comparable[] array) {
        if (array == null || array.length <= 1) return;
        if (isSorted(array)) return;
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - i - 1; j++)
                //前面元素大于后面元素，将两元素交换
                if (great(array[j], array[j + 1])) exChange(array, j, j + 1);
            //每次循环后判断数组是否有序，有序就结束循化，无序重复上述步骤。
            if (isSorted(array)) return;
        }
    }

    /**
     * <p> 快速排序
     * 核心思想：
     * 1.选择一个基数(选择数组的第一个元素)
     * 2.将数组中小于该基数的元素放到左边，大于该基数的元素放到右边
     * 3.通过迭代法对两边的数组依次进行如上操作
     * <p>
     * 具体步骤
     * 1.选择数组的第一个元素为基数
     * 2.然后数组首尾各一个指针
     * 3.从首部选择从左向右依次找大于基数的数
     * 4.从尾部选择从右向左依次找小于基数的数进行交换
     * 5.递归此过程
     * 演示
     * 3 10 6 7 5 8 2 9 4 1
     * 3  1 6 7 5 8 2 9 4 10
     * 3  1 2 7 5 8 6 9 4 10
     * 1  2 3 7 5 8 6 9 4 10
     * 1  2 3 7 5 4 6 9 8 10
     * 1  2 3 6 5 4 7 9 8 10
     * 1  2 3 4 5 6 7 9 8 10
     * 1  2 3 4 5 6 7 9 8 10
     *
     * @param array 要排序的数组
     * @param low   起始位置
     * @param high  结束位置
     * @return void
     * @Author huangy
     * @description //TODO 快速排序
     * @date 9:45 上午 2020/9/14
     **/
    public static void quickSort(Comparable[] array, int low, int high) {
        if (array == null || array.length <= 1) return;
        if (high <= low) return;
        int index = partition(array, low, high);
        //左边继续快排
        quickSort(array, index + 1, high);
        //右边继续快排
        quickSort(array, low, index);
    }

    /**
     * @param array 一趟快排
     * @param low   其实位置
     * @param high  结束位置
     * @return int 基数的位置
     * @Author huangy
     * @description //TODO 快速排序
     * @date 8:18 下午 2020/9/21
     **/
    public static int partition(Comparable[] array, int low, int high) {
        //选择基类，为数组的第一个元素
        Comparable base = array[low];
        int i = low;
        int j = high + 1;
        while (true) {
            //循环选择左边比基数大的元素
            while (less(array[++i], base)) if (i == high) break;
            //循环选择右边比基数小的元素
            while (great(array[--j], base)) if (j == low) break;
            if (i >= j) break;
            //交换元素
            exChange(array, i, j);
        }
        //将基数元素放到数组中合适的位置
        exChange(array, low, j);
        return j;
    }

    /**
     * <p> 对于重复值较多的数组的排序方法
     * 分为三个区域的快速排序方法的改进
     * |V| ****************** |
     * | <V  | =V | **** | >V |
     * | <V  | =V | >V |
     * 步骤演示
     * | 5 | 6 | 5 | 1 | 3 | 5 | 3 | 6 | 1 | 5 | 5 | 7 | 6 | 5 | 1 |
     * | 1 | 1 | 3 | 3 | 1 | 5 | 5 | 5 | 5 | 5 | 5 | 6 | 7 | 6 | 6 |
     * | 1 | 1 | 1 | 3 | 3 | 5 | 5 | 5 | 5 | 5 | 5 | 6 | 7 | 6 | 6 |
     * | 1 | 1 | 1 | 3 | 3 | 5 | 5 | 5 | 5 | 5 | 5 | 6 | 7 | 6 | 6 |
     * | 1 | 1 | 1 | 3 | 3 | 5 | 5 | 5 | 5 | 5 | 5 | 6 | 6 | 6 | 7 |
     * | 1 | 1 | 1 | 3 | 3 | 5 | 5 | 5 | 5 | 5 | 5 | 6 | 6 | 6 | 7 |
     *
     * @param array 要排序的数组
     * @param low   起始位置
     * @param high  结束位置
     * @return void
     * @Author huangy
     * @description //TODO 3-way快速排序
     * @date 10:50 上午 2020/9/23
     **/
    public static void quick3Way(Comparable[] array, int low, int high) {
        if (array == null || array.length <= 1) return;
        if (high <= low) return;
        int index = low + 1;
        //基数
        Comparable base = array[low];
        int lt = low;
        int gt = high;
        while (index <= gt) {
            int cmp = array[index].compareTo(base);
            //当前元素array[index]小于base，交换lt和index对应元素，lt，index自增1
            if (cmp < 0) exChange(array, index++, lt++);
                //当前元素array[index]大于base，交换gt和index，gt自增1
            else if (cmp > 0) exChange(array, index, gt--);
                //当前元素array[index]等于base，index自增
            else index++;
        }
        printArray(array);
        quick3Way(array, low, lt - 1);
        quick3Way(array, gt + 1, high);
    }

    /**
     * <p> 在快速排序思想的基础上，进行快速查找
     *
     * @param array 数组
     * @param k     位置
     * @return Comparable 找到的元素
     * @Author huangy
     * @description //TODO 查找在数组中第几小的元素
     * @date 10:55 上午 2020/9/22
     **/
    public static Comparable randomQuickSelect(Comparable[] array, int k) {
        if (k < 0 || k > array.length - 1) return null;
        //打乱数组
        StdRandom.shuffle(array);
        int i = 0;
        int j = array.length - 1;
        while (i <= j) {
            int index = partition(array, i, j);
            if (index < k) i = index + 1;
            else if (index > k) j = index - 1;
            else return array[k];
        }
        return null;
    }

    /**
     * <p> 插入排序
     * 1.保持前面数组有序，这里是确保前两个数组有序。
     * 2.循环将后面的元素插入到前面数组的适当位置，保持原数组保持有序
     * 3.每次循环后判断数组是否有序
     * 4.如果数组有序，结束排序，如果无序继续循环直到数组有序。
     *
     * @param array 要排序的数组
     * @return void
     * @Author huangy
     * @description //TODO 插入排序
     * @date 9:24 下午 2020/8/26
     **/
    public static void insertSort(Comparable[] array) {
        if (array == null || array.length <= 1) return;
        if (isSorted(array)) return;
        for (int i = 0; i < array.length; i++) {
            //通过循化比较将元素放到数组前面数组适当位置，是数组有序
            while (i - 1 >= 0 && less(array[i], array[i - 1])) exChange(array, i, --i);
            if (isSorted(array)) return;
        }
    }

    /**
     * <p> 插入排序的优化
     * 在插入排序中，影响排序时间的是逆序对
     * 什么是逆序对：1325486
     * 3-2逆序对，它们是使数组无序的原因
     * 所以逆序对越少，插入排序交换次数就越少，时间就越短
     * 所以先拉大交换距离，进行几次少数交换，然后将距离缩短，最后缩短到1
     * 在前面几次交换后，逆序对数量降低，最后当距离为1时进行的交换次数也
     * 对大大降低，这样就能提高排序效率。
     *
     * @param array 要排序的数组
     * @return void
     * @Author huangy
     * @description //TODO 希尔排序
     * @date 5:29 下午 2020/8/30
     **/
    public static void shellSort(Comparable[] array) {
        if (array == null || array.length <= 1) return;
        if (isSorted(array)) return;
        int N = array.length;
        int h = 1;
        while (h < N / 3) h = 3 * h + 1;
        while (h > 0) {
            for (int i = h; i < N; i++)
                for (int j = i; j - h >= 0 && great(array[j - h], array[j]); j -= h)
                    exChange(array, j - h, j);
            if (isSorted(array)) return;
            h = h / 3;
        }
    }

    /**
     * <p> 归并排序
     * > 核心思想：将两个有序数组合并成一个有序数组
     * > 分步思想
     * 1.将一个数组一分为二分为两个数组
     * 2.先对一边进行排序
     * 3.再对另一边进行排序
     * 4.将两个排完序的数组合并为更大的有序数组
     * <p>
     * 算法具体实现
     * 按照上述的思想
     * 1.将数组一分为二
     * 2.通过递归的思想，将分开的数组也分别一分为二
     * 3.直到每个子数组都是有序的：何时数组有序，就是分到每个数组只有一个元素的时候数组是有序的
     * 4.然后在将一个个有序数组通过递归的方式进行合并，合并为更大的有序数组，直到最后只剩一个最大的有序数组
     * <p>
     * 图示
     * ----- 5 7 8 1 4 3 9 10 0 11
     * |     5 7 8 1 4|3 9 10 0 11
     * 分 ---5 7 8|1 4|3 9 10|0 11
     * |     5 7|8|1|4|3 9|10|0|11
     * ----- 5|7|8|1|4|3|9|10|0|11
     * --------------------------
     * ----- 5|7|8|1|4|3|9|10|0|11
     * |     5 7|8|1 4|3 9|10|0 11
     * 合 ---5 7 8|1 4|3 9 10|0 11
     * |     1 4 5 7 8|0 3 9 10 11
     * ----- 0 1 3 4 5 7 8 9 10 11
     *
     * @param array 要排序的数组
     * @param temp  临时数组
     * @param low   起始位置
     * @param high  结束位置
     * @return void
     * @Author huangy
     * @description //TODO 归并排序 - 先分后并
     * @date 9:12 上午 2020/9/7
     **/
    public static void mergeSort(Comparable[] array, Comparable[] temp, int low, int high) {
        if (array == null || array.length <= 1) return;
        //if (isSorted(array)) return;
        //递归结束条件
        if (high <= low) return;
        int mid = (low + high) >>> 1;
        //左边递归
        mergeSort(array, temp, low, mid);
        //右边递归
        mergeSort(array, temp, mid + 1, high);
        //查看数组是否有序，有序就跳过合并
        if (less(array[mid], array[mid + 1])) return;
        //合并有序数组
        merge(array, temp, low, mid, high);
    }

    /**
     * <p>
     * 核心思想：与之前的归并排序不一样，不用递归
     * 而是直接通过合并的方式进行数组的排序
     * > 分步思想
     * 1.先将数组元素两个为一组合并
     * 2.再将数组元素两个两个的合并
     * 3.按照1,2,4,8的顺序合并下去
     * 直到最后循环结束
     *
     * @param array 要排序的数组
     * @return void
     * @Author huangy
     * @description //TODO 归并排序 - 直接合并
     * @date 11:32 上午 2020/9/14
     **/
    public static void mergeSort(Comparable[] array) {
        if (array == null || array.length <= 1) return;
        //if (isSorted(array)) return;
        int N = array.length;
        Comparable[] temp = new Comparable[N];
        for (int size = 1; size < N; size = size + size)
            for (int i = 0; i < N - size; i += size + size) {
                int mid = i + size - 1;
                merge(array, temp, i, mid, Math.min(i + size + size - 1, N - 1));
            }
    }

    /**
     * @param array 要合并数组的
     * @param temp  临时存储数组
     * @param low   起始位置
     * @param mid   中间位置
     * @param high  结束位置
     * @return void
     * @Author huangy
     * @description //TODO 将两边有序的数组合并为整个有序的数组
     * @date 9:58 上午 2020/9/11
     **/
    private static void merge(Comparable[] array, Comparable[] temp, int low, int mid, int high) {
        //将原数组的数据拷贝到临时数组
        if (high + 1 - low >= 0) System.arraycopy(array, low, temp, low, high + 1 - low);
        //循环比较，合并数组
        int i = low;//左指针
        int j = mid + 1;//右指针
        for (int k = low; k <= high; k++) {
            //左边已经都排好序，直接取左边元素
            if (i > mid) array[k] = temp[j++];
                //右边已经排好序，直接取右边元素
            else if (j > high) array[k] = temp[i++];
                //左边元素大于右边则取右边元素
            else if (great(temp[i], temp[j])) array[k] = temp[j++];
                //右边元素大于左边则取左边预算
            else array[k] = temp[i++];
        }
    }

    /**
     * @param array 要交换元素的数组
     * @param i     要交换的第一个元素位置
     * @param j     要交换的第二个元素位置
     * @return void
     * @Author huangy
     * @description //TODO 交换数组的两个元素
     * @date 8:41 下午 2020/8/27
     **/
    public static void exChange(Comparable[] array, int i, int j) {
        Comparable temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * @param array   二维数组
     * @param row1    第一个元素行位置
     * @param column1 第一个元素列位置
     * @param row2    第二个元素行位置
     * @param column2 第二个元素列位置
     * @return void
     * @Author huangy
     * @description //TODO 二维数组交换两个元素
     * @date 9:38 下午 2020/11/8
     **/
    public static void exChange(Comparable[][] array, int row1, int column1, int row2, int column2) {
        Comparable temp = array[row1][column1];
        array[row1][column1] = array[row2][column2];
        array[row2][column2] = temp;
    }

    /**
     * @param array 被判断的数组
     * @return boolean
     * @Author huangy
     * @description //TODO 判断数组是否有序
     * @date 9:21 下午 2020/8/27
     **/
    public static boolean isSorted(Comparable[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            if (great(array[i], array[i + 1])) return false;
        }
        return true;
    }

    /**
     * @param v 值v
     * @param w 值w
     * @return boolean
     * @Author huangy
     * @description //TODO 判断v是否小于w
     * @date 9:30 上午 2020/8/28
     **/
    public static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    /**
     * @param v 值v
     * @param w 值w
     * @return boolean
     * @Author huangy
     * @description //TODO 判断v是否等于w
     * @date 9:30 上午 2020/8/28
     **/
    public static boolean equals(Comparable v, Comparable w) {
        return v.compareTo(w) == 0;
    }

    /**
     * @param v 值v
     * @param w 值w
     * @return boolean
     * @Author huangy
     * @description //TODO 判断v是大于w
     * @date 9:30 上午 2020/8/28
     **/
    public static boolean great(Comparable v, Comparable w) {
        return v.compareTo(w) > 0;
    }

    /**
     * @param array 要打印的数组
     * @return void
     * @Author huangy
     * @description //TODO 打印数组
     * @date 4:43 下午 2020/8/30
     **/
    public static void printArray(Comparable[] array) {
        for (Comparable c : array) {
            if (c == null) continue;
            System.out.print("|" + c);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        //需要排序的数组
        Integer[] array = {1, 9, -10, 45, 6, 5, 23, 43, 4, 10};
//        array = new Integer[]{8, 7, 9, 5, 4, 3, 2, 1};
        mergeSort(array);
        printArray(array);
        //array = new Integer[]{2, 1};
        //testBubblingSort(array);
        //testInsertSort(array);
        //testShellSort(array);
//        testMergeSort(array);
        //testQuickSelect(array);
        //testQuickSort(array);
//        testQuick3Way();
//        testMerge();
    }

    /**
     * 测试冒泡排序
     *
     * @param array 要排序的数组
     */
    private static void testBubblingSort(Integer[] array) {
        printArray(array);
        bubblingSort(array);
        printArray(array);
    }

    /**
     * 测试冒泡排序
     *
     * @param array 要排序的数组
     */
    private static void testInsertSort(Integer[] array) {
        printArray(array);
        insertSort(array);
        printArray(array);
    }

    /**
     * 测试希尔排序
     *
     * @param array 要排序的数组
     */
    private static void testShellSort(Integer[] array) {
        printArray(array);
        shellSort(array);
        printArray(array);
    }

    /**
     * 测试归并排序
     *
     * @param array 要排序的数组
     */
    private static void testMergeSort(Integer[] array) {
        printArray(array);
        //mergeSort(array);
        mergeSort(array, new Integer[array.length], 0, array.length - 1);
        printArray(array);
    }

    /**
     * 测试归并排序中的合并方法
     **/
    private static void testMerge() {
        int N = 100;
        Integer[] array = createRandomArray(N);
        printArray(array);
        long startTime = new Date().getTime();
        Integer[] tempArray = new Integer[N];
        mergeSort(array, tempArray, 0, N - 1);
        printArray(array);
        long endTime = new Date().getTime();
        long runTime = endTime - startTime;
        System.out.println("方法执行时间是: " + runTime);
    }

    /**
     * 测试快速排序
     *
     * @param array 被排序的数组
     */
    private static void testQuickSort(Comparable[] array) {
        //打乱数组
        StdRandom.shuffle(array);
        printArray(array);
        quickSort(array, 0, array.length - 1);
        printArray(array);
    }

    /**
     * 测试快速查找
     *
     * @param array 被查找的数组
     */
    private static void testQuickSelect(Comparable[] array) {
        printArray(array);
        int index = 10;
        Comparable comparable = randomQuickSelect(array, index);
        System.out.println("数组第" + index + "个元素是" + comparable);
    }

    /**
     * 测试三区快速排序
     */
    private static void testQuick3Way() {
        Integer[] array = new Integer[]{5, 6, 5, 1, 3, 5, 3, 6, 1, 5, 5, 7, 6, 5, 1};
        printArray(array);
        quick3Way(array, 0, array.length - 1);
        printArray(array);
    }

    /**
     * @param N 指定长度
     * @return void
     * @Author huangy
     * @description //TODO 生成指定长度的随机数组
     * @date 上午10:18 2021/5/25
     **/
    public static Integer[] createRandomArray(int N) {
        Integer[] array = new Integer[N];
        for (int i = 0; i < N; i++) {
            array[i] = random.nextInt(N);
        }
        return array;
    }

}
